package com.cat.binaryTree;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/all-nodes-distance-k-in-binary-tree/description/?envType=problem-list-v2&envId=binary-tree
 * @create 2025/9/21 20:44
 * @since JDK17
 */

public class Solution58 {
    HashMap<TreeNode, TreeNode> map = new HashMap<>();
    List<Integer> ans = new ArrayList<>();
    int k;
    void dfs(TreeNode root, TreeNode fa) {
        if (root == null) {
            return;
        }
        map.put(root, fa);
        dfs(root.left, root);
        dfs(root.right, root);
    }

    void f(TreeNode root, TreeNode fa, int d) {
        if (d == k) {
            ans.add(root.val);
            return;
        }
        if (root.left != fa) {
            f(root.left, root, d + 1);
        }
        if (root.right != fa) {
            f(root.right, root, d + 1);
        }
    }

    public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
        this.k = k;
        dfs(root, root);
        f(root, root, 0);
        return ans;
    }
}
